package com.shm.leetcode;

/**
 * 1995. 统计特殊四元组
 * 给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
 *
 * nums[a] + nums[b] + nums[c] == nums[d] ，且
 * a < b < c < d
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,6]
 * 输出：1
 * 解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。
 * 示例 2：
 *
 * 输入：nums = [3,3,6,4,5]
 * 输出：0
 * 解释：[3,3,6,4,5] 中不存在满足要求的四元组。
 * 示例 3：
 *
 * 输入：nums = [1,1,1,3,5]
 * 输出：4
 * 解释：满足要求的 4 个四元组如下：
 * - (0, 1, 2, 3): 1 + 1 + 1 == 3
 * - (0, 1, 3, 4): 1 + 1 + 3 == 5
 * - (0, 2, 3, 4): 1 + 1 + 3 == 5
 * - (1, 2, 3, 4): 1 + 1 + 3 == 5
 *
 *
 * 提示：
 *
 * 4 <= nums.length <= 50
 * 1 <= nums[i] <= 100
 * @author SHM
 */
public class CountQuadruplets {
    /**
     * 方法一：直接枚举
     * 思路与算法
     *
     * 最简单的方法是直接枚举四个下标 a, b, c, da,b,c,d 并进行判断。
     * 复杂度分析
     *
     * 时间复杂度：O(n^4)O(n
     * 4
     *  )，其中 nn 是数组 \textit{nums}nums 的长度。
     *
     * 空间复杂度：O(1)O(1)。
     * @param nums
     * @return
     */
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int a = 0; a < n-3; a++) {
            for (int b = a+1; b < n-2; b++) {
                for (int c = b+1; c < n-1; c++) {
                    for (int d = c+1; d < n; d++) {
                        if (nums[a]+nums[b]+nums[c]==nums[d]){
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
